{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum One Bit Operations to Make Integers Zero"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #memoization #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #记忆化搜索 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumOneBitOperations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #使整数变为 0 的最少操作次数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数 <code>n</code>，你需要重复执行多次下述操作将其转换为 <code>0</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>翻转 <code>n</code> 的二进制表示中最右侧位（第 <code>0</code> 位）。</li>\n",
    "\t<li>如果第 <code>(i-1)</code> 位为 <code>1</code> 且从第 <code>(i-2)</code> 位到第 <code>0</code> 位都为 <code>0</code>，则翻转 <code>n</code> 的二进制表示中的第 <code>i</code> 位。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回将 <code>n</code> 转换为 <code>0</code> 的最小操作次数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>3 的二进制表示为 \"11\"\n",
    "\"<strong>1</strong>1\" -&gt; \"<strong>0</strong>1\" ，执行的是第 2 种操作，因为第 0 位为 1 。\n",
    "\"0<strong>1</strong>\" -&gt; \"0<strong>0</strong>\" ，执行的是第 1 种操作。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>6 的二进制表示为 \"110\".\n",
    "\"<strong>1</strong>10\" -&gt; \"<strong>0</strong>10\" ，执行的是第 2 种操作，因为第 1 位为 1 ，第 0 到 0 位为 0 。\n",
    "\"01<strong>0</strong>\" -&gt; \"01<strong>1</strong>\" ，执行的是第 1 种操作。\n",
    "\"0<strong>1</strong>1\" -&gt; \"0<strong>0</strong>1\" ，执行的是第 2 种操作，因为第 0 位为 1 。\n",
    "\"00<strong>1</strong>\" -&gt; \"00<strong>0</strong>\" ，执行的是第 1 种操作。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-one-bit-operations-to-make-integers-zero](https://leetcode.cn/problems/minimum-one-bit-operations-to-make-integers-zero/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-one-bit-operations-to-make-integers-zero](https://leetcode.cn/problems/minimum-one-bit-operations-to-make-integers-zero/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3', '6']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            ans ^= n\n",
    "            n = n >> 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        inv = 0\n",
    "        while n: \n",
    "            inv = inv ^ n\n",
    "            n = n >> 1\n",
    "        return inv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        if not n:return 0\n",
    "        head = 1<<int(math.log2(n))\n",
    "        return head + self.minimumOneBitOperations((n^head)^(head>>1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "                return 0\n",
    "        return n ^ self.minimumOneBitOperations(n >> 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "      x = 1\n",
    "      while x <= n:\n",
    "        x <<= 1\n",
    "      x >>= 1\n",
    "      ans = 0\n",
    "      t = 0\n",
    "      while x:\n",
    "        ans, t = (ans | (t ^ (n & x))), (n & x) ^ t\n",
    "        x >>= 1\n",
    "        t >>= 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        def f(x):\n",
    "            if x < 2:\n",
    "                return x\n",
    "            n = x.bit_length() - 2\n",
    "            t = 1 << n\n",
    "            m = x & (t - 1)\n",
    "            if x >> n == 3:\n",
    "                return 2 * t + f(m)\n",
    "            s = 4 * t \n",
    "            if m == 0:\n",
    "                return s - 1\n",
    "            t = 1 << m.bit_length() - 1\n",
    "            return s - 2 * t + f(m & (t - 1))\n",
    "            \n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n > 0:\n",
    "            ans ^= n\n",
    "            n >>= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        ans = 0\n",
    "        while n:\n",
    "            ans ^= n\n",
    "            n >>= 1\n",
    "        return ans\n",
    "\n",
    "        #格雷码."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "      ans = 0\n",
    "      while n:\n",
    "        ans ^= n\n",
    "        n >>= 1\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        digit = n.bit_length()\n",
    "        return (1 << digit) - 1 - self.minimumOneBitOperations(n - (1 << (digit - 1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BitOperation:\n",
    "    def __init__(self):\n",
    "        return\n",
    "\n",
    "    @staticmethod\n",
    "    def sum_xor(n):\n",
    "        # 模板：计算 [0, x] 区间证书的异或和\n",
    "        if n % 4 == 0:\n",
    "            return n\n",
    "        # (4*i)^(4*i+1)^(4*i+2)^(4*i+3)=0\n",
    "        elif n % 4 == 1:\n",
    "            return 1  # n^(n-1)\n",
    "        elif n % 4 == 2:\n",
    "            return n + 1  # n^(n-1)^(n-2)\n",
    "        return 0  # n^(n-1)^(n-2)^(n-3)\n",
    "\n",
    "    @staticmethod\n",
    "    def sum_xor_2(n):\n",
    "        # 模板：计算 [0, x] 区间证书的异或和\n",
    "        if n % 4 == 0:\n",
    "            return n\n",
    "        # (4*i)^(4*i+1)^(4*i+2)^(4*i+3)=0\n",
    "        elif n % 4 == 1:\n",
    "            return n ^ (n - 1)\n",
    "        elif n % 4 == 2:\n",
    "            return n ^ (n - 1) ^ (n - 2)\n",
    "        return n ^ (n - 1) ^ (n - 2) ^ (n - 3)\n",
    "\n",
    "    @staticmethod\n",
    "    def graycode_to_integer(graycode):\n",
    "        # 格雷码转二进制\n",
    "        graycode_len = len(graycode)\n",
    "        binary = list()\n",
    "        binary.append(graycode[0])\n",
    "        for i in range(1, graycode_len):\n",
    "            if graycode[i] == binary[i - 1]:\n",
    "                b = 0\n",
    "            else:\n",
    "                b = 1\n",
    "            binary.append(str(b))\n",
    "        return int(\"0b\" + ''.join(binary), 2)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        \n",
    "        return BitOperation().graycode_to_integer(bin(n)[2:])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        temp=str(bin(n)[2:])\n",
    "        res=0\n",
    "        sign=1\n",
    "        for i in range(len(temp)):\n",
    "            if temp[i]=='1':\n",
    "                if (sign%2)==1:\n",
    "                    res+=2**(len(temp)-i)-1\n",
    "                else:\n",
    "                    res-=2**(len(temp)-i)-1\n",
    "                sign+=1\n",
    "        \n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def dfs(i):\n",
    "    # 只有两个方向 最高位的1后面变成10000 然后消除最高位的1\n",
    "    # 以及将这个数字变化为10000 直接套公式2 ^ (i + 1) - 1\n",
    "    if i < 2:\n",
    "        return i\n",
    "    if i & (i - 1) == 0:\n",
    "        return 2 * i - 1\n",
    "    tmp = i\n",
    "    # 最高位\n",
    "    while tmp & (tmp - 1) != 0:\n",
    "        tmp &= tmp - 1\n",
    "    return 2 * tmp - 1 - dfs(i - tmp)\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        # 2 ^ i次方的数字是很好找到规律的\n",
    "        \n",
    "        return dfs(n)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def dfs(i):\n",
    "    # 只有两个方向 最高位的1后面变成10000 然后消除最高位的1\n",
    "    # 以及将这个数字变化为10000 直接套公式2 ^ (i + 1) - 1\n",
    "    if i < 2:\n",
    "        return i\n",
    "    tmp = i\n",
    "    # 最高位\n",
    "    while tmp & (tmp - 1) != 0:\n",
    "        tmp &= tmp - 1\n",
    "    return 2 * tmp - 1 - dfs(i - tmp)\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        # 2 ^ i次方的数字是很好找到规律的\n",
    "        # 即操作数为2 * (i + 1) - 1\n",
    "        \n",
    "        return dfs(n)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        # 计算 n 的二进制长度\n",
    "        l = len(bin(n)) - 2\n",
    "        return (1 << l) - 1 - self.minimumOneBitOperations(n ^ (1 << (l - 1)))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        n = bin(n)[2:]\n",
    "        ans = 2 ** (len(n) - 1)\n",
    "        test = '1'\n",
    "        for i in range(1, len(n)):\n",
    "            if n[i] == test:\n",
    "                test = '0'\n",
    "            else:\n",
    "                test = '1'\n",
    "                ans += 2 ** (len(n) - i - 1)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        def f(x):\n",
    "            if x == 1:\n",
    "                return 1\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            m = 1\n",
    "            while x >> m:\n",
    "                m += 1\n",
    "            res = x - (1 << (m - 1))\n",
    "            if res == 0:\n",
    "                return (1 << m) - 1\n",
    "            return h(res, m-1) + f(1 << (m-2)) + 1\n",
    "        def g(x):\n",
    "            if x == 1:\n",
    "                return 0\n",
    "            if x == 0:\n",
    "                return 1\n",
    "            m = 1\n",
    "            while x >> m:\n",
    "                m += 1\n",
    "            res = x - (1 << (m - 1))\n",
    "            return f(res)\n",
    "        def h(x, k):\n",
    "            m = 1\n",
    "            while x >> m:\n",
    "                m += 1\n",
    "            if m == k:\n",
    "                return g(x)\n",
    "            else:\n",
    "                ans = g(x)\n",
    "                for i in range(m, k):\n",
    "                    ans = ans + 1 + f(1 << (i - 1))\n",
    "                return ans\n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self,n):\n",
    "        operations = 0\n",
    "        bin_n = bin(n)[2:][::-1]  # Convert n to binary and reverse it for easy access\n",
    "        l = len(bin_n)\n",
    "        bin_n = bin_n[::-1]\n",
    "        print(bin_n)\n",
    "        def get_one(now):\n",
    "            if now >= l:\n",
    "                return 0\n",
    "            if bin_n[now] == '0':\n",
    "                return get_one(now+1) +  2**(l-now-1)\n",
    "            return solve(now+1)\n",
    "        def solve(now):\n",
    "            if now >= l:\n",
    "                return 0\n",
    "            if now == l - 1:\n",
    "                if bin_n[now] == '1':\n",
    "                    return 1\n",
    "                return 0\n",
    "            if bin_n[now] == '0':\n",
    "                return solve(now + 1)\n",
    "            if bin_n[now + 1] == '1':\n",
    "                return 2 ** (l - now - 1) + solve(now + 2)\n",
    "            else:\n",
    "                return min(2 ** (l - now) - 1 + solve(now + 2) , get_one(now+1) + 2**(l-now-1))\n",
    "\n",
    "        return solve(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mp={};\n",
    "class Solution:\n",
    "    def dfs(self,x:int) -> int:\n",
    "        if x<=1:\n",
    "            return x\n",
    "        if x==2:\n",
    "            return 3\n",
    "        if x==3:\n",
    "            return 2\n",
    "        if x in mp.keys():\n",
    "            return mp[x]\n",
    "        bit=1\n",
    "        a=1<<bit\n",
    "        while a<=x:\n",
    "            bit +=1\n",
    "            a=1<<bit\n",
    "        b=1<<(bit-2)\n",
    "        c=b-1\n",
    "        if x&b!=0:\n",
    "            now1=self.dfs(c&x)+1+self.dfs(b)\n",
    "        else:\n",
    "            d=1<<(bit-3)\n",
    "            y=(1<<(bit-1))+(1<<(bit-2))+(1<<(bit-3))\n",
    "            now1=abs(self.dfs(c&x)-self.dfs(d))+1+self.dfs(c&y)+1+self.dfs(b)\n",
    "        mp[x]=now1\n",
    "        return mp[x]\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        return self.dfs(n)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "@cache\n",
    "def dfs(i):\n",
    "    # 只有两个方向 最高位的1后面变成10000 然后消除最高位的1\n",
    "    # 以及将这个数字变化为10000 直接套公式2 ^ (i + 1) - 1\n",
    "    if i < 2:\n",
    "        return i\n",
    "    if i & (i - 1) == 0:\n",
    "        return 2 * i - 1\n",
    "    tmp = i\n",
    "    while tmp & (tmp - 1) != 0:\n",
    "        tmp &= tmp - 1\n",
    "    return 2 * tmp - 1 - dfs(i - tmp)\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "        # 2 ^ i次方的数字是很好找到规律的\n",
    "        \n",
    "        return dfs(n)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    '''\r\n",
    "    从左边第二位起，将每位与左边一位解码后的值异或，\r\n",
    "    作为该位解码后的值（最左边一位依然不变）。直到最低位。\r\n",
    "    依次异或转换后的值（二进制数）就是格雷码转换后二进制码的值。\r\n",
    "    '''\r\n",
    "    def minimumOneBitOperations0(self, n: int) -> int:\r\n",
    "        if not n:return 0\r\n",
    "        head = 1<<int(math.log2(n))\r\n",
    "        return head + self.minimumOneBitOperations((n^head)^(head>>1))\r\n",
    "        \r\n",
    "    # 递归格雷码\r\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\r\n",
    "        if not n:return 0\r\n",
    "        return n^self.minimumOneBitOperations(n>>1)\r\n",
    "        \r\n",
    "    \r\n",
    "    # 大数版本\r\n",
    "    def minimumOneBitOperations3(self, n: int) -> int:\r\n",
    "        gray_to_byte8 = [0, 1, 3, 2, 7, 6, 4, 5, 15, 14, 12, 13, 8, 9, 11, 10, 31, 30, 28, 29, \\\r\n",
    "            24, 25, 27, 26, 16, 17, 19, 18, 23, 22, 20, 21, 63, 62, 60, 61, 56, \\\r\n",
    "            57, 59, 58, 48, 49, 51, 50, 55, 54, 52, 53, 32, 33, 35, 34, 39, 38, \\\r\n",
    "            36, 37, 47, 46, 44, 45, 40, 41, 43, 42, 127, 126, 124, 125, 120, 121, \\\r\n",
    "            123, 122, 112, 113, 115, 114, 119, 118, 116, 117, 96, 97, 99, 98, 103, \\\r\n",
    "            102, 100, 101, 111, 110, 108, 109, 104, 105, 107, 106, 64, 65, 67, 66, \\\r\n",
    "            71, 70, 68, 69, 79, 78, 76, 77, 72, 73, 75, 74, 95, 94, 92, 93, 88, 89, \\\r\n",
    "            91, 90, 80, 81, 83, 82, 87, 86, 84, 85, 255, 254, 252, 253, 248, 249, \\\r\n",
    "            251, 250, 240, 241, 243, 242, 247, 246, 244, 245, 224, 225, 227, 226, \\\r\n",
    "            231, 230, 228, 229, 239, 238, 236, 237, 232, 233, 235, 234, 192, 193, \\\r\n",
    "            195, 194, 199, 198, 196, 197, 207, 206, 204, 205, 200, 201, 203, 202, \\\r\n",
    "            223, 222, 220, 221, 216, 217, 219, 218, 208, 209, 211, 210, 215, 214, \\\r\n",
    "            212, 213, 128, 129, 131, 130, 135, 134, 132, 133, 143, 142, 140, 141, \\\r\n",
    "            136, 137, 139, 138, 159, 158, 156, 157, 152, 153, 155, 154, 144, 145, \\\r\n",
    "            147, 146, 151, 150, 148, 149, 191, 190, 188, 189, 184, 185, 187, 186, \\\r\n",
    "            176, 177, 179, 178, 183, 182, 180, 181, 160, 161, 163, 162, 167, 166, \\\r\n",
    "            164, 165, 175, 174, 172, 173, 168, 169, 171, 170]\r\n",
    "        if not n:return 0\r\n",
    "        head = 0\r\n",
    "        ls = []\r\n",
    "        for i in int(n).to_bytes(int((math.log2(n))//8+1),\"big\"):\r\n",
    "            ls.append(gray_to_byte8[i^(head<<7)])\r\n",
    "            head = ls[-1]&1\r\n",
    "        return int.from_bytes(ls,'big')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumOneBitOperations(self, n: int) -> int:\n",
    "\n",
    "        @cache\n",
    "        def f(x):\n",
    "            if x == 0:\n",
    "                return 0\n",
    "            if x & (x - 1) == 0:\n",
    "                return 2 * x - 1\n",
    "            cur_len = x.bit_length()\n",
    "            high = 1 << (cur_len - 1)\n",
    "            if x & (1 << (cur_len - 2)) == 0:\n",
    "                idx = cur_len - 3\n",
    "                while (1 << idx) & x == 0:\n",
    "                    idx -= 1\n",
    "                tmp = x & ((1 << idx) - 1)\n",
    "                return f(tmp) + f(1 << idx) + 1 + f(high + (1 << idx + 1))\n",
    "                \n",
    "            else:\n",
    "                return f(((1 << (cur_len - 2)) - 1) & x) + f(high >> 1) + 1\n",
    "        \n",
    "        return f(n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
